package org.algorithm.二师兄.数组.三月.第二周;

import java.util.Arrays;

/**
 * @author 二师兄
 * @date 2022/03/08 11:38 PM
 * @description:        周四作业
 *
 *  <p>
 *      给你一个整数数组 nums 和一个整数 k 。请你向 nums 中追加 k 个 未 出现在 nums 中的、互不相同 的 正 整数，并使结果数组的元素和 最小 。
 *
 *      返回追加到 nums 中的 k 个整数之和。
 *
 *      案例：
 *          输入：nums = [1,4,25,10,25], k = 2
 *          输出：5
 *          解释：在该解法中，向数组中追加的两个互不相同且未出现的正整数是 2 和 3 。
 *          nums 最终元素和为 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70 ，这是所有情况中的最小值。
 *          所以追加到数组中的两个整数之和是 2 + 3 = 5 ，所以返回 5 。
 *  </p>
 *
 * uri:  https://leetcode-cn.com/problems/append-k-integers-with-minimal-sum/
 */
public class 向数组中追加K个整数 {

    public static void main(String[] args) {
        int[] nums = {1,4,25,10,25};
        System.out.println(minimalKSum(nums, 2));
    }


    public static long minimalKSum(int[] nums, int k) {
        Arrays.sort(nums);

        long ans = 0;
        int left = 0, right = 1;

        // 若第一个数字是1
        if (nums[0] == 1) {
            while (k > 0 && right < nums.length) {
                if (nums[left] == nums[right] || nums[left] + 1 == nums[right]) {
                    left++;
                    right++;
                    continue;
                }
                if (nums[right] - nums[left] - 1 <= k) {
                    ans += getSum(nums[left], nums[right]);
                    k -= nums[right] - nums[left] - 1;
                }else {
                    ans += getSum(nums[left], nums[left] + k + 1);
                    k = 0;
                }
                left++; right++;
            }

            // 遍历完成后， K还不为0 ， 证明还能加
            int more = nums[nums.length - 1] + 1;
            while (k > 0) {
                ans+=more;
                more++;
                k--;
            }
            return ans;
        }

        if (nums[0] - 1 >= k) {
            ans += getSum(0, 1 + k);
            return ans;
        } else {
            ans += getSum(0, nums[0]);
            k -= nums[0] - 1;
        }

        //如此往复，遍历数组内的相邻两个数字，并且加到`ans`上
        while (k > 0 && right < nums.length) {
            if (nums[left] == nums[right] || nums[left] + 1 == nums[right]) {
                left++;
                right++;
                continue;
            }
            if (nums[right] - nums[left]- 1 <= k) {
                ans += getSum(nums[left], nums[right]);
                k -= nums[right] - nums[left] - 1;
            } else {
                ans += getSum(nums[left], nums[left] + k + 1);
                k = 0;
            }
            left++;
            right++;
        }

        //若数组遍历结束后，k仍然不为0，则从最大值 + 1开始，加上后面的数字，直到k为0
        int more = nums[nums.length - 1] + 1;
        while (k > 0) {
            ans += more;
            more++;
            k--;
        }
        return ans;
    }

    private static long getSum(int left, int right) {
        int quan = right - left - 1;
        long sum = 0;
        sum += (long) (right + left) * quan / 2;
        return sum;
    }
}
